# LeetCode 641、设计循环双端队列

# 一、题目描述

设计实现双端队列。你的实现需要支持以下操作：

MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。

# 二、题目解析

1、初始化容量 capacity = k + 1 ，并建立大小为 capacity 的数组 arr；

2、设置两个指针 front 和 rear

3、front 指向当前队首元素的位置

4 、rear 指向当前队尾元素的下一个位置，即下一个入队元素的位置

5、判空条件：front = = rear

6、判满条件：(rear + 1) % capacity == front，也就是 rear 再后移一位就碰到了 front ，因为是循环存储的，所以 rear + 1 可能会比 capacity 大，取模之后再和 front 比较

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class MyCircularDeque {

    // capacity 表示数组的容量，它的大小为 k + 1
    private int capacity ;

    // front 表示队头的位置
    private int front;

    // rear 表示队列尾部的下一个位置
    private int rear;

    // 这里使用数组来设计循环双端队列
    private int[] arr;


    public MyCircularDeque(int k) {

        // 需要空出一个额外的空间
        // 当队列中的元素有 k 个时，代表队列已满
        capacity = k + 1;

        // 这里使用数组来设计循环双端队列，数组的容量为 capacity
        // 即在数组中会空出一个额外的空间来不存储任何元素
        // 因为这样才能合理的区分出【队列为空】和【队列已满】这两种情况
        arr = new int[capacity];

        // 初始化队头指针
        front = 0;

        // 初始化队尾指针
        rear = 0;
    }
    
    // 在双端队列的队头添加元素 value
    public boolean insertFront(int value) {
        // 首先判断队列是否已满，没有其它的剩余空间
        // 如果队列已满，那么元素无法添加进去
        if(isFull()){
           //  返回 false
           return false;
        }

        // front 向前移动
        // 由于 front 会移动到数组的最前面，如果再向前移动会出界
        // 那么这个时候就需要将 front 挪到数组结尾的位置
        // 可以通过取余运算来实现循环移动的这个操作
        front = ( front - 1  + capacity) % capacity;

        // 添加元素 value 到 front 这个位置
        arr[front] = value;

        // 添加元素成功，返回 true
        return true;

    }
    
    // 在双端队列的队尾添加元素 value
    public boolean insertLast(int value) {

        // 首先判断队列是否已满，没有其它的剩余空间
        // 如果队列已满，那么元素无法添加进去
        if(isFull()){
           //  返回 false
           return false;
        }

        // 添加元素 value 到 rear 这个位置
        arr[rear] = value;

        // rear 向后移动
        // 由于 rear 会移动到数组的最尾部，如果再向后移动会出界
        // 那么这个时候就需要将 rear 挪到数组开头的位置
        // 可以通过取余运算来实现循环移动的这个操作
        rear = ( rear + 1 ) % capacity;

        // 添加元素成功，返回 true
        return true;

    }
    
    // 删除双端队列的队头元素
    public boolean deleteFront() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可删，返回 false
            return false;
        }

        // 队头指针向后移动
        front = ( front + 1 ) % capacity;

        // 删除元素成功，返回 true
        return true;

    }
    
    // 删除双端队列的队尾元素
    public boolean deleteLast() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可删，返回 false
            return false;
        }

        // 队尾指针向前移动
        rear = ( rear - 1 + capacity ) % capacity;

        // 删除元素成功，返回 true
        return true;
    }
    
    public int getFront() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可选，根据题目要求返回 -1
            return -1;
        }

        // 否则返回 front 指向的元素就行
        return arr[front];

    }
    
    public int getRear() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可选，根据题目要求返回 -1
            return -1;
        }

        // 否则返回 rear 位置的前一个元素就行
        return arr[(rear - 1 + capacity) % capacity];
    }
    
    // 判断队列是否为空
    public boolean isEmpty() {
        // front 和 rear 指向同一个位置时，队列为空
        return front == rear;
    }
    
    public boolean isFull() {
        // 当队尾指针向后移动一个位置后，指向了队头时，那么说明队列已满
        return ( rear + 1 ) % capacity == front;
    }
}

# 2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class MyCircularDeque {

public:
    // capacity 表示数组的容量，它的大小为 k + 1
    int capacity;

    // front 表示队头的位置
    int front;

    // rear 表示队列尾部的下一个位置
    int rear;

    // 这里使用数组来设计循环双端队列
    vector<int> arr;


    MyCircularDeque(int k) {

        // 需要空出一个额外的空间
        // 当队列中的元素有 k 个时，代表队列已满
        capacity = k + 1;

        // 这里使用数组来设计循环双端队列，数组的容量为 capacity
        // 即在数组中会空出一个额外的空间来不存储任何元素
        // 因为这样才能合理的区分出【队列为空】和【队列已满】这两种情况
        arr = vector<int>(capacity);

        // 初始化队头指针
        front = 0;

        // 初始化队尾指针
        rear = 0;
    }

    // 在双端队列的队头添加元素 value
    bool insertFront(int value) {
        // 首先判断队列是否已满，没有其它的剩余空间
        // 如果队列已满，那么元素无法添加进去
        if(isFull()){
           //  返回 false
           return false;
        }

        // front 向前移动
        // 由于 front 会移动到数组的最前面，如果再向前移动会出界
        // 那么这个时候就需要将 front 挪到数组结尾的位置
        // 可以通过取余运算来实现循环移动的这个操作
        front =  ( front - 1 + capacity ) % capacity;

        // 添加元素 value 到 front 这个位置
        arr[front] = value;

        // 添加元素成功，返回 true
        return true;

    }

    // 在双端队列的队尾添加元素 value
    bool insertLast(int value) {

        // 首先判断队列是否已满，没有其它的剩余空间
        // 如果队列已满，那么元素无法添加进去
        if(isFull()){
           //  返回 false
           return false;
        }

        // 添加元素 value 到 rear 这个位置
        arr[rear] = value;

        // rear 向后移动
        // 由于 rear 会移动到数组的最尾部，如果再向后移动会出界
        // 那么这个时候就需要将 rear 挪到数组开头的位置
        // 可以通过取余运算来实现循环移动的这个操作
        rear =  (rear + 1) % capacity;

        // 添加元素成功，返回 true
        return true;

    }

    // 删除双端队列的队头元素
    bool deleteFront() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可删，返回 false
           return false;
        }

        // 队头指针向后移动
        front = (front + 1) % capacity;

        // 删除元素成功，返回 true
        return true;

    }

    // 删除双端队列的队尾元素
    bool deleteLast() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可删，返回 false
            return false;
        }

        // 队尾指针向前移动
        rear = (rear - 1 + capacity) % capacity;

        // 删除元素成功，返回 true
        return true;
    }

    int getFront() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可选，根据题目要求返回 -1
            return - 1;
        }

        // 否则返回 front 指向的元素就行
        return arr[front];

    }

    int getRear() {
        // 首先判断队列是否为空
        if(isEmpty()){
            // 队列为空的话那就没有元素可选，根据题目要求返回 -1
            return -1;
        }

        // 否则返回 rear 位置的前一个元素就行
        return arr[(rear - 1 + capacity) % capacity];
    }

    // 判断队列是否为空
    bool isEmpty() {
        // front 和 rear 指向同一个位置时，队列为空
        return front == rear;
    }

    bool isFull() {
        // 当队尾指针向后移动一个位置后，指向了队头时，那么说明队列已满
        return (rear + 1) % capacity == front;
    }
};

# 3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
class MyCircularDeque:

    # capacity 表示数组的容量，它的大小为 k + 1

    # front 表示队头的位置

    # rear 表示队列尾部的下一个位置

    # 这里使用数组来设计循环双端队列

    def __init__(self, k: int):

        # 需要空出一个额外的空间
        # 当队列中的元素有 k 个时，代表队列已满
        self.capacity = k + 1

        # 这里使用数组来设计循环双端队列，数组的容量为 capacity
        # 即在数组中会空出一个额外的空间来不存储任何元素
        # 因为这样才能合理的区分出【队列为空】和【队列已满】这两种情况
        self.arr = [0] * self.capacity

        # 初始化队头指针
        self.front = 0

        # 初始化队尾指针
        self.rear = 0
    

    # 在双端队列的队头添加元素 value
    def insertFront(self, value: int) -> bool:
        # 首先判断队列是否已满，没有其它的剩余空间
        # 如果队列已满，那么元素无法添加进去
        if self.isFull() :
           #  返回 false
           return False

        # front 向前移动
        # 由于 front 会移动到数组的最前面，如果再向前移动会出界
        # 那么这个时候就需要将 front 挪到数组结尾的位置
        # 可以通过取余运算来实现循环移动的这个操作
        self.front =  ( self.front - 1 + self.capacity ) % self.capacity

        # 添加元素 value 到 front 这个位置
        self.arr[self.front] = value

        # 添加元素成功，返回 true
        return True

    # 在双端队列的队尾添加元素 value
    def insertLast(self, value: int) -> bool:

        # 首先判断队列是否已满，没有其它的剩余空间
        # 如果队列已满，那么元素无法添加进去
        if self.isFull() :
           #  返回 false
           return False

        # 添加元素 value 到 rear 这个位置
        self.arr[self.rear] = value

        # rear 向后移动
        # 由于 rear 会移动到数组的最尾部，如果再向后移动会出界
        # 那么这个时候就需要将 rear 挪到数组开头的位置
        # 可以通过取余运算来实现循环移动的这个操作
        self.rear =  (self.rear + 1) % self.capacity

        # 添加元素成功，返回 true
        return True


    # 删除双端队列的队头元素
    def deleteFront(self) -> bool:
        # 首先判断队列是否为空
        if self.isEmpty():
            # 队列为空的话那就没有元素可删，返回 false
            return False

        # 队头指针向后移动
        self.front = (self.front + 1) % self.capacity

        # 删除元素成功，返回 true
        return True
 

    # 删除双端队列的队尾元素
    def deleteLast(self) -> bool:
        # 首先判断队列是否为空
        if self.isEmpty():
            # 队列为空的话那就没有元素可删，返回 false
            return False

        # 队尾指针向前移动
        self.rear = (self.rear - 1 + self.capacity) % self.capacity

        # 删除元素成功，返回 true
        return True
    

    def getFront(self) -> int:
        if self.isEmpty():
            # 队列为空的话那就没有元素可选，根据题目要求返回 -1
            return -1

        # 否则返回 front 指向的元素就行
        return self.arr[self.front]

    def getRear(self) -> int:
        # 首先判断队列是否为空
        if self.isEmpty():
            # 队列为空的话那就没有元素可选，根据题目要求返回 -1
            return -1

        # 否则返回 rear 位置的前一个元素就行
        return self.arr[(self.rear - 1 + self.capacity) % self.capacity]
    

    # 判断队列是否为空
    def isEmpty(self) -> bool:
        # front 和 rear 指向同一个位置时，队列为空
        return self.front == self.rear
    

    def isFull(self) -> bool:
        # 当队尾指针向后移动一个位置后，指向了队头时，那么说明队列已满
        return (self.rear + 1) % self.capacity == self.front

# 四、复杂度分析

时间复杂度：O(1)

空间复杂度：O(k)

← LeetCode 739、每日温度 LeetCode 264、丑数II →